package copy;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class HaveCircularDependency {
    public List<Integer> haveCircularDependency(int n, int[][] prerequisites) {
        int[] inDegrees = new int[n];
        List<List<Integer>> adjLists = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adjLists.add(new ArrayList<>());
        }

        for (int i = 0; i < prerequisites.length; i++) {
            int cur = prerequisites[i][0];
            int next = prerequisites[i][1];
            inDegrees[next]++;
            adjLists.get(cur).add(next);
        }

        for (int i = 0; i < inDegrees.length; i++) {
            if (inDegrees[i] == 0) {
                queue.offer(i);
            }
        }
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int cur = queue.poll();
                ans.add(cur);
                List<Integer> adjList = adjLists.get(cur);
                for (int adj : adjList) {
                    inDegrees[adj]--;
                    if (inDegrees[adj] == 0) {
                        queue.offer(adj);
                    }
                }
            }
        }
        if (ans.size() == n) {
            return ans;
        } else {
            return null;
        }
    }

    public static void main(String[] args) {
        HaveCircularDependency solution = new HaveCircularDependency();
        int[][] p = {{0, 2}, {1, 2}, {2, 3}, {2, 4}};
        List<Integer> ans = solution.haveCircularDependency(5, p);
        for (Integer an : ans) {
            System.out.println(an);
        }
    }
}
